SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Mutilated chessboard problem</title>

</head>

Mutilated chessboard problem

</h1>

</header>

The mutilated chessboard problem is a <a href="Tiling_puzzle" title="Tiling puzzle">tiling puzzle</a> posed by <a href="Max_Black" title="Max Black">Max Black</a> in 1946 that asks:

<blockquote>Suppose a standard 8×8 <a href="Chessboard" title="Chessboard">chessboard</a> (or <a href="Checkerboard" title="Checkerboard">checkerboard</a>) has two diagonally opposite corners removed, leaving 62 squares. Is it possible to place 31 <a href="Dominoes" title="Dominoes">dominoes</a> of size 2×1 so as to cover all of these squares?</blockquote>

It is an <a href="Impossible_puzzle" class="mw-redirect" title="Impossible puzzle">impossible puzzle</a>: there is no <a href="Domino_tiling" title="Domino tiling">domino tiling</a> meeting these conditions. One proof of its impossibility uses the fact that, with the corners removed, the chessboard has 32 squares of one color and 30 of the other, but each domino must cover equally many squares of each color. More generally, if any two squares are removed from the chessboard, the rest can be tiled by dominoes if and only if the removed squares are of different colors. This problem has been used as a test case for <a href="Automated_reasoning" title="Automated reasoning">automated reasoning</a>, <a href="Creativity" title="Creativity">creativity</a>, and the <a href="Philosophy_of_mathematics" title="Philosophy of mathematics">philosophy of mathematics</a>.

<div class="mw-heading mw-heading2"><h2 id="History">History</h2></div>

The mutilated chessboard problem is an instance of <a href="Domino_tiling" title="Domino tiling">domino tiling</a> of grids and <a href="Polyomino" title="Polyomino">polyominoes</a>, also known as "dimer models", a general class of problems whose study in <a href="Statistical_mechanics" title="Statistical mechanics">statistical mechanics</a> dates to the work of <a href="Ralph_H._Fowler" class="mw-redirect" title="Ralph H. Fowler">Ralph H. Fowler</a> and <a href="George_Stanley_Rushbrooke" title="George Stanley Rushbrooke">George Stanley Rushbrooke</a> in 1937.<a href="#cite_note-fowler-rushbrooke-1">[1]</a> Domino tilings also have a long history of practical use in pavement design and the arrangement of <a href="Tatami" title="Tatami">tatami</a> flooring.<a href="#cite_note-tatami-2">[2]</a>

The mutilated chessboard problem itself was proposed by philosopher <a href="Max_Black" title="Max Black">Max Black</a> in his book Critical Thinking (1946), with a hint at the coloring-based solution to its impossibility.<a href="#cite_note-black-3">[3]</a><a href="#cite_note-robinson-4">[4]</a> It was popularized in the 1950s through later discussions by <a href="Solomon_W._Golomb" title="Solomon W. Golomb">Solomon W. Golomb</a> (1954),<a href="#cite_note-golomb-5">[5]</a> <a href="George_Gamow" title="George Gamow">George Gamow</a> and Marvin Stern (1958),<a href="#cite_note-gamow-stern-6">[6]</a> <a href="Claude_Berge" title="Claude Berge">Claude Berge</a> (1958),<a href="#cite_note-robinson-4">[4]</a><a href="#cite_note-berge-7">[7]</a> and <a href="Martin_Gardner" title="Martin Gardner">Martin Gardner</a> in his <a href="Scientific_American" title="Scientific American">Scientific American</a> column "<a href="List_of_Martin_Gardner_Mathematical_Games_columns" title="List of Martin Gardner Mathematical Games columns">Mathematical Games</a>" (1957).<a href="#cite_note-gardner-8">[8]</a>

The use of the mutilated chessboard problem in <a href="Automated_reasoning" title="Automated reasoning">automated reasoning</a> stems from a proposal for its use by <a href="John_McCarthy_(computer_scientist)" title="John McCarthy (computer scientist)">John McCarthy</a> in 1964.<a href="#cite_note-mccarthy64-9">[9]</a><a href="#cite_note-kerber-pollet-10">[10]</a> It has also been studied in <a href="Cognitive_science" title="Cognitive science">cognitive science</a> as a test case for creative insight,<a href="#cite_note-kaplan-simon-11">[11]</a><a href="#cite_note-akin-akin-12">[12]</a><a href="#cite_note-bgvd-13">[13]</a> Black's original motivation for the problem.<a href="#cite_note-black-3">[3]</a> In the <a href="Philosophy_of_mathematics" title="Philosophy of mathematics">philosophy of mathematics</a>, it has been examined in studies of the nature of <a href="Mathematical_proof" title="Mathematical proof">mathematical proof</a>.<a href="#cite_note-mackenzie-14">[14]</a><a href="#cite_note-kerber-15">[15]</a><a href="#cite_note-tanswell-16">[16]</a><a href="#cite_note-starikova-vanbendegem-17">[17]</a>

<div class="mw-heading mw-heading2"><h2 id="Solution">Solution</h2></div>

The puzzle is impossible to complete. A domino placed on the chessboard will always cover one white square and one black square. Therefore, any collection of dominoes placed on the board will cover equal numbers of squares of each color. But any two opposite squares have the same color: both black or both white. If they are removed, there will be fewer squares of that color and more of the other color, making the numbers of squares of each color unequal and the board impossible to cover.<a href="#cite_note-gardner-8">[8]</a> The same idea shows that no <a href="Domino_tiling" title="Domino tiling">domino tiling</a> can exist whenever any two squares of the same color (not just the opposite corners) are removed from the chessboard.<a href="#cite_note-honsberger-18">[18]</a>

Several other proofs of impossibility have also been found. A proof by <a href="Shmuel_Winograd" title="Shmuel Winograd">Shmuel Winograd</a> starts with induction. In a given tiling of the board, if a row has an odd number of squares not covered by vertical dominoes from the previous row, then an odd number of vertical dominoes must extend into the next row. The first row trivially has an odd number of squares (namely, 7) not covered by dominoes of the previous row. Thus, by induction, each of the seven pairs of consecutive rows houses an odd number of vertical dominoes, producing an odd total number. By the same reasoning, the total number of horizontal dominoes must also be odd. As the sum of two odd numbers, the total number of dominoes—vertical and horizontal—must be even. But to cover the mutilated chessboard, 31 dominoes are needed, an odd number.<a href="#cite_note-mccarthy99-19">[19]</a><a href="#cite_note-mendelsohn-20">[20]</a> Another method counts the edges of each color around the boundary of the mutilated chessboard. Their numbers must be equal in any tileable region of the chessboard, because each domino has three edges of each color, and each internal edge between dominoes pairs off boundaries of opposite colors. However, the mutilated chessboard has more edges of one color than the other.<a href="#cite_note-propp-21">[21]</a>

If two squares of opposite colors are removed, then the remaining board can always be tiled with dominoes; this result is Gomory's theorem,<a href="#cite_note-watkins-22">[22]</a> after mathematician <a href="Ralph_E._Gomory" title="Ralph E. Gomory">Ralph E. Gomory</a>, whose proof was published in 1973.<a href="#cite_note-honsberger-18">[18]</a><a href="#cite_note-mendelsohn-20">[20]</a> Gomory's theorem can be proven using a <a href="Hamiltonian_cycle" class="mw-redirect" title="Hamiltonian cycle">Hamiltonian cycle</a> of the <a href="Grid_graph" class="mw-redirect" title="Grid graph">grid graph</a> formed by the chessboard squares. The removal of any two oppositely colored squares splits this cycle into two paths with an even number of squares each. Both of these paths are easy to partition into dominoes by following them.<a href="#cite_note-watkins-22">[22]</a> Gomory's theorem is specific to the removal of only one square of each color. Removing larger numbers of squares, with equal numbers of each color, can result in a region that has no domino tiling, but for which coloring-based impossibility proofs do not work.<a href="#cite_note-wright-23">[23]</a>

<div class="mw-heading mw-heading2"><h2 id="Application_to_automated_reasoning">Application to automated reasoning</h2></div>

Domino tiling problems on <a href="Polyomino" title="Polyomino">polyominoes</a>, such as the mutilated chessboard problem, can be solved in <a href="Polynomial_time" class="mw-redirect" title="Polynomial time">polynomial time</a>, either by converting them into problems in <a href="Group_theory" title="Group theory">group theory</a>,<a href="#cite_note-propp-21">[21]</a><a href="#cite_note-thurston-24">[24]</a> or as instances of <a href="Bipartite_matching" class="mw-redirect" title="Bipartite matching">bipartite matching</a>. In the latter formulation, one obtains a <a href="Bipartite_graph" title="Bipartite graph">bipartite graph</a> with a vertex for each available chessboard square and an edge for every pair of adjacent squares; the problem is to find a system of edges that touches each vertex exactly once. As in the coloring-based proof of the impossibility of the mutilated chessboard problem, the fact that this graph has more vertices of one color than the other implies that it fails the necessary conditions of <a href="Hall's_marriage_theorem" title="Hall's marriage theorem">Hall's marriage theorem</a>, so no matching exists.<a href="#cite_note-wright-23">[23]</a><a href="#cite_note-urquhart-25">[25]</a><a href="#cite_note-bpmb-26">[26]</a> The problem can also be solved by formulating it as a <a href="Constraint_satisfaction_problem" title="Constraint satisfaction problem">constraint satisfaction problem</a>, and applying <a href="Semidefinite_programming" title="Semidefinite programming">semidefinite programming</a> to a <a href="Relaxation_(approximation)" title="Relaxation (approximation)">relaxation</a>.<a href="#cite_note-semidefinite-27">[27]</a>

In 1964, <a href="John_McCarthy_(computer_scientist)" title="John McCarthy (computer scientist)">John McCarthy</a> proposed the mutilated chessboard as a hard problem for <a href="Automated_proof" class="mw-redirect" title="Automated proof">automated proof</a> systems, formulating it in <a href="First-order_logic" title="First-order logic">first-order logic</a> and asking for a system that can automatically determine the unsolvability of this formulation.<a href="#cite_note-mccarthy64-9">[9]</a> Most considerations of this problem provide solutions "in the conceptual sense" that do not apply to McCarthy's logic formulation of the problem.<a href="#cite_note-andrews-bishop-28">[28]</a> Despite the existence of general methods such as those based on graph matching, it is exponentially hard for <a href="Resolution_(logic)" title="Resolution (logic)">resolution</a> to solve McCarthy's logical formulation of the problem,<a href="#cite_note-dantchev-riis-29">[29]</a><a href="#cite_note-alekhnovich-30">[30]</a><a href="#cite_note-razborov-31">[31]</a> highlighting the need for methods in <a href="Artificial_intelligence" title="Artificial intelligence">artificial intelligence</a> that can automatically change to a more suitable problem representation<a href="#cite_note-korf-32">[32]</a> and for <a href="Knowledge_representation" class="mw-redirect" title="Knowledge representation">knowledge representation</a> systems that can manage the equivalences between different representations.<a href="#cite_note-kerber-pollet-10">[10]</a> Short proofs are possible using resolution with additional variables,<a href="#cite_note-krishnamurthy-33">[33]</a> or in stronger proof systems allowing the expression of avoidable tiling patterns that can prune the search space.<a href="#cite_note-clausal-34">[34]</a> Higher-level <a href="Proof_assistant" title="Proof assistant">proof assistants</a> are capable of handling the coloring-based impossibility proof directly; these include <a href="Isabelle_(proof_assistant)" title="Isabelle (proof assistant)">Isabelle</a>,<a href="#cite_note-isabelle-35">[35]</a> the <a href="Mizar_system" title="Mizar system">Mizar system</a>,<a href="#cite_note-mizar-36">[36]</a> and <a href="Nqthm" title="Nqthm">Nqthm</a>.<a href="#cite_note-subramanian-37">[37]</a>

<div class="mw-heading mw-heading2"><h2 id="Related_problems">Related problems</h2></div>

</div><div class="thumbinner" style="width:178px"><table cellpadding="0" cellspacing="0"><tbody><tr><td colspan="8" rowspan="8"><div class="chess-pieces notheme" style="position:relative"><div style="top:0px;left:0px"></div><div style="top:154px;left:154px"></div></div></td></tr></tbody></table><div class="thumbcaption"> Wazir's tour problem

</div></div></div><style data-mw-deduplicate="TemplateStyles:r1276579313">

/* start https://en.wikipedia.org/ */

.mw-parser-output .chessboard table{font-size:88%;border:1px #c8ccd1 solid;padding:0;margin:auto}.mw-parser-output .chessboard table tr{vertical-align:middle}.mw-parser-output .chessboard table td{padding:0;vertical-align:inherit;text-align:center}.mw-parser-output .chessboard table td[rowspan]{text-align:unset}.mw-parser-output .chessboard .chess-pieces div:not(.pcs-image-wrapper){position:absolute;z-index:3}

/* end https://en.wikipedia.org/ */

</style>

A similar problem asks if a <a href="Wazir_(chess)" title="Wazir (chess)">wazir</a> starting at a corner square of an ordinary chessboard can visit every square exactly once, and finish at the opposite corner square. The wazir is a <a href="Fairy_chess_piece" title="Fairy chess piece">fairy chess piece</a> that can move only one square vertically or horizontally (not diagonally). Using similar reasoning to the mutilated chessboard problem's classic solution, this wazir's tour does not exist. For example, if the initial square is white, as each move alternates between black and white squares, the final square of any complete tour is black. However, the opposite corner square is white.<a href="#cite_note-wazir-38">[38]</a>

This sort of tour of a chessboard also forms the basis of a type of puzzle called <a href="Numbrix" class="mw-redirect" title="Numbrix">Numbrix</a>, which asks for a tour in which the positions of certain squares match given clues.<a href="#cite_note-hanson-nash-39">[39]</a> The impossibility of a corner-to-corner tour shows the impossibility of a Numbrix puzzle with the clues 1 in one corner and 64 in the opposite corner.

<a href="De_Bruijn's_theorem" title="De Bruijn's theorem">De Bruijn's theorem</a> concerns the impossibility of packing certain <a href="Cuboid" title="Cuboid">cuboids</a> into a larger cuboid. For instance, it is impossible, according to this theorem, to fill a 6 × 6 × 6 box with 1 × 2 × 4 cuboids. The proof uses a similar chessboard-coloring argument to the mutilated chessboard problem.<a href="#cite_note-debruijn-40">[40]</a>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFFowlerRushbrooke1937" class="citation cs2"><a href="Ralph_H._Fowler" class="mw-redirect" title="Ralph H. Fowler">Fowler, R. H.</a>; <a href="George_Stanley_Rushbrooke" title="George Stanley Rushbrooke">Rushbrooke, G. S.</a> (1937), "An attempt to extend the statistical theory of perfect solutions", <a href="Transactions_of_the_Faraday_Society" class="mw-redirect" title="Transactions of the Faraday Society">Transactions of the Faraday Society</a>, 33: 1272, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1039%2Ftf9373301272">10.1039/tf9373301272</a></cite>

</li>

<li id="cite_note-tatami-2"><a href="#cite_ref-tatami_2-0">^</a> <cite id="CITEREFEricksonRuskeySchurchWoodcock2010" class="citation cs2">Erickson, Alejandro; <a href="Frank_Ruskey" title="Frank Ruskey">Ruskey, Frank</a>; Schurch, Mark; Woodcock, Jennifer (2010), "Auspicious tatami mat arrangements", in <a href="My_T._Thai" title="My T. Thai">Thai, My T.</a>; <a href="Sartaj_Sahni" title="Sartaj Sahni">Sahni, Sartaj</a> (eds.), Computing and Combinatorics, 16th Annual International Conference, COCOON 2010, Nha Trang, Vietnam, July 19–21, 2010, Proceedings, Lecture Notes in Computer Science, vol. 6196, Springer, pp. 288–297, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1103.3309">1103.3309</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-642-14031-0_32">10.1007/978-3-642-14031-0_32</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-642-14030-3</bdi>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2720105">2720105</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:6603662">6603662</a></cite>

</li>

<li id="cite_note-black-3">^ <a href="#cite_ref-black_3-0">a</a> <a href="#cite_ref-black_3-1">b</a> <cite id="CITEREFBlack1946" class="citation cs2"><a href="Max_Black" title="Max Black">Black, Max</a> (1946), Critical Thinking: An Introduction To Logic And Scientific Method, Prentice Hall, pp. 157, 433</cite>

</li>

<li id="cite_note-robinson-4">^ <a href="#cite_ref-robinson_4-0">a</a> <a href="#cite_ref-robinson_4-1">b</a> <cite id="CITEREFRobinson1991" class="citation cs2">Robinson, J. A. (1991), "Formal and Informal Proofs", in Boyer, Robert S. (ed.), Automated Reasoning: Essays in Honor of Woody Bledsoe, Automated Reasoning Series, vol. 1, Springer Netherlands, pp. 267–282, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-94-011-3488-0_13">10.1007/978-94-011-3488-0_13</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-94-010-5542-0</bdi></cite>; see especially Section 13.1, "The mutilated chess board problem", <a rel="nofollow" class="external text" href="https://books.google.com/books?id=guSoCAAAQBAJ&pg=PA271">pp. 271–274</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20220718074354/https://books.google.com/books?id=guSoCAAAQBAJ&pg=PA271">Archived</a> 2022-07-18 at the <a href="Wayback_Machine" title="Wayback Machine">Wayback Machine</a>.

</li>

<li id="cite_note-golomb-5"><a href="#cite_ref-golomb_5-0">^</a> <cite id="CITEREFGolomb1954" class="citation cs2"><a href="Solomon_W._Golomb" title="Solomon W. Golomb">Golomb, S. W.</a> (1954), "Checker boards and polyominoes", <a href="The_American_Mathematical_Monthly" title="The American Mathematical Monthly">The American Mathematical Monthly</a>, 61 (10): 675–682, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1080%2F00029890.1954.11988548">10.1080/00029890.1954.11988548</a>, <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2307321">2307321</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0067055">0067055</a></cite>

</li>

<li id="cite_note-gamow-stern-6"><a href="#cite_ref-gamow-stern_6-0">^</a> <cite id="CITEREFGamowStern1958" class="citation cs2"><a href="George_Gamow" title="George Gamow">Gamow, George</a>; Stern, Marvin (1958), "Domino game", Puzzle-Math, Viking Press, pp. 87–90</cite>

</li>

<li id="cite_note-berge-7"><a href="#cite_ref-berge_7-0">^</a> <cite id="CITEREFBerge1958" class="citation cs2 cs1-prop-foreign-lang-source"><a href="Claude_Berge" title="Claude Berge">Berge, Claude</a> (1958), Théorie des graphes et ses applications (in French), Dunod, p. 176</cite>

</li>

<li id="cite_note-gardner-8">^ <a href="#cite_ref-gardner_8-0">a</a> <a href="#cite_ref-gardner_8-1">b</a> <cite id="CITEREFGardner1957" class="citation cs2"><a href="Martin_Gardner" title="Martin Gardner">Gardner, Martin</a> (February 1957), "An assortment of maddening puzzles", Mathematical Games, <a href="Scientific_American" title="Scientific American">Scientific American</a>, 196 (2): 152–158, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1038%2Fscientificamerican0257-152">10.1038/scientificamerican0257-152</a>, <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/24941903">24941903</a></cite>; for solution, see

<cite id="CITEREFGardner1957" class="citation cs2"><a href="Martin_Gardner" title="Martin Gardner">Gardner, Martin</a> (March 1957), "Some old and new versions of ticktacktoe, plus the answers to last month's puzzles", Mathematical Games, <a href="Scientific_American" title="Scientific American">Scientific American</a>, 196 (3): 160–168, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1038%2Fscientificamerican0357-160">10.1038/scientificamerican0357-160</a>, <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/24940785">24940785</a></cite>. Reprinted in My Best Mathematical and Logic Puzzles (Dover Publications, 1994), pages 2 and 39.

</li>

<li id="cite_note-mccarthy64-9">^ <a href="#cite_ref-mccarthy64_9-0">a</a> <a href="#cite_ref-mccarthy64_9-1">b</a> <cite id="CITEREFMcCarthy1964" class="citation cs2"><a href="John_McCarthy_(computer_scientist)" title="John McCarthy (computer scientist)">McCarthy, John</a> (July 17, 1964), <a rel="nofollow" class="external text" href="https://jmc.stanford.edu/articles/toughnut.html">A tough nut for proof procedures</a>, Stanford AI Memo, vol. 16, <a rel="nofollow" class="external text" href="https://web.archive.org/web/20210516113211/http://jmc.stanford.edu/articles/toughnut.html">archived</a> from the original on 2021-05-16, retrieved 2022-07-18</cite>

</li>

<li id="cite_note-kerber-pollet-10">^ <a href="#cite_ref-kerber-pollet_10-0">a</a> <a href="#cite_ref-kerber-pollet_10-1">b</a> <cite id="CITEREFKerberPollet2005" class="citation cs2">Kerber, Manfred; Pollet, Martin (2005), <a rel="nofollow" class="external text" href="https://www.cs.bham.ac.uk/~mmk/papers/05-MKM.html">"A tough nut for mathematical knowledge management"</a>, in Kohlhase, Michael (ed.), Mathematical Knowledge Management, 4th International Conference, MKM 2005, Bremen, Germany, July 15-17, 2005, Revised Selected Papers, Lecture Notes in Computer Science, vol. 3863, Springer, pp. 81–95, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F11618027_6">10.1007/11618027_6</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-31430-1</bdi></cite>

</li>

<li id="cite_note-kaplan-simon-11"><a href="#cite_ref-kaplan-simon_11-0">^</a> <cite id="CITEREFKaplanSimon1990" class="citation cs2">Kaplan, Craig A.; <a href="Herbert_A._Simon" title="Herbert A. Simon">Simon, Herbert A.</a> (July 1990), "In search of insight", <a href="Cognitive_Psychology_(journal)" title="Cognitive Psychology (journal)">Cognitive Psychology</a>, 22 (3): 374–419, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0010-0285%2890%2990008-r">10.1016/0010-0285(90)90008-r</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:54334455">54334455</a></cite>

</li>

<li id="cite_note-akin-akin-12"><a href="#cite_ref-akin-akin_12-0">^</a> <cite id="CITEREFAkinAkin1998" class="citation cs2">Akin, Ömer; Akin, Cem (January 1998), "On the process of creativity in puzzles, inventions, and designs", Automation in Construction, 7 (2–3): 123–138, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fs0926-5805%2897%2900057-5">10.1016/s0926-5805(97)00057-5</a></cite>

</li>

<li id="cite_note-bgvd-13"><a href="#cite_ref-bgvd_13-0">^</a> <cite id="CITEREFBilalićGrafVaciDanek2019" class="citation cs2">Bilalić, Merim; Graf, Mario; Vaci, Nemanja; Danek, Amory H. (August 2019), "When the solution is on the doorstep: Better solving performance, but diminished aha! experience for chess experts on the mutilated checkerboard problem", <a href="Cognitive_Science_(journal)" title="Cognitive Science (journal)">Cognitive Science</a>, 43 (8): e12771, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1111%2Fcogs.12771">10.1111/cogs.12771</a>, <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/31446653">31446653</a></cite>

</li>

<li id="cite_note-mackenzie-14"><a href="#cite_ref-mackenzie_14-0">^</a> <cite id="CITEREFMacKenzie2005" class="citation cs2">MacKenzie, Donald (2005), "Computing and the cultures of proving", <a href="Philosophical_Transactions_of_the_Royal_Society" title="Philosophical Transactions of the Royal Society">Philosophical Transactions of the Royal Society</a>, 363 (1835): 2335–2350, <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2005RSPTA.363.2335M">2005RSPTA.363.2335M</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1098%2Frsta.2005.1649">10.1098/rsta.2005.1649</a>, <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/30039731">30039731</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2197653">2197653</a>, <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/16188609">16188609</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:18225791">18225791</a></cite>

</li>

<li id="cite_note-kerber-15"><a href="#cite_ref-kerber_15-0">^</a> <cite id="CITEREFKerber2014" class="citation cs2">Kerber, Manfred (2014), "A proof and some representations", in Wyatt, Jeremy L.; Petters, Dean D.; Hogg, David C. (eds.), From Animals to Robots and Back: Reflections on Hard Problems in the Study of Cognition, A Collection in Honour of Aaron Sloman, Cognitive Systems Monographs, vol. 22, Springer International Publishing, pp. 65–73, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-319-06614-1_5">10.1007/978-3-319-06614-1_5</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-319-06613-4</bdi></cite>

</li>

<li id="cite_note-tanswell-16"><a href="#cite_ref-tanswell_16-0">^</a> <cite id="CITEREFTanswell2015" class="citation cs2">Tanswell, Fenner (2015), "A problem with the dependence of informal proofs on formal proofs", <a href="Philosophia_Mathematica" title="Philosophia Mathematica">Philosophia Mathematica</a>, Series III, 23 (3): 295–310, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1093%2Fphilmat%2Fnkv008">10.1093/philmat/nkv008</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=3404036">3404036</a></cite>

</li>

<li id="cite_note-starikova-vanbendegem-17"><a href="#cite_ref-starikova-vanbendegem_17-0">^</a> <cite id="CITEREFStarikovaVan_Bendegem2021" class="citation cs2">Starikova, Irina; Van Bendegem, Jean Paul (2021), <a rel="nofollow" class="external text" href="https://www.researchgate.net/publication/341220441">"Revisiting the mutilated chessboard or the many roles of a picture"</a>, Logique et Analyse, 64 (255): 289–312, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2143%2FLEA.255.0.3290192">10.2143/LEA.255.0.3290192</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=4396339">4396339</a>, <a rel="nofollow" class="external text" href="https://web.archive.org/web/20220719004449/https://www.researchgate.net/publication/341220441_Revisiting_the_mutilated_chessboard_or_the_many_roles_of_a_picture">archived</a> from the original on 2022-07-19, retrieved 2022-07-19</cite>

</li>

<li id="cite_note-honsberger-18">^ <a href="#cite_ref-honsberger_18-0">a</a> <a href="#cite_ref-honsberger_18-1">b</a> <cite id="CITEREFHonsberger1973" class="citation cs2"><a href="Ross_Honsberger" title="Ross Honsberger">Honsberger, R.</a> (1973), "Gomory's theorem", Mathematical Gems I, Mathematical Association of America, pp. 65–67</cite>

</li>

<li id="cite_note-mccarthy99-19"><a href="#cite_ref-mccarthy99_19-0">^</a> <cite id="CITEREFMcCarthy1999" class="citation cs2"><a href="John_McCarthy_(computer_scientist)" title="John McCarthy (computer scientist)">McCarthy, John</a> (1999), <a rel="nofollow" class="external text" href="http://jmc.stanford.edu/articles/creative.html">"Creative Solutions to Problems"</a>, AISB Workshop on Artificial Intelligence and Creativity, <a rel="nofollow" class="external text" href="https://web.archive.org/web/20181023181750/http://jmc.stanford.edu/articles/creative.html">archived</a> from the original on 2018-10-23, retrieved 2007-04-27</cite>

</li>

<li id="cite_note-mendelsohn-20">^ <a href="#cite_ref-mendelsohn_20-0">a</a> <a href="#cite_ref-mendelsohn_20-1">b</a> <cite id="CITEREFMendelsohn2004" class="citation cs2">Mendelsohn, N. S. (2004), "Tiling with dominoes", <a href="The_College_Mathematics_Journal" title="The College Mathematics Journal">The College Mathematics Journal</a>, 35 (2): 115–120, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F4146865">10.2307/4146865</a>, <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/4146865">4146865</a></cite>. Mendelsohn credits the original publication of Gomory's theorem to <a href="#CITEREFHonsberger1973">Honsberger (1973)</a>.

</li>

<li id="cite_note-propp-21">^ <a href="#cite_ref-propp_21-0">a</a> <a href="#cite_ref-propp_21-1">b</a> <cite id="CITEREFPropp2021" class="citation cs2"><a href="Jim_Propp" title="Jim Propp">Propp, Jim</a> (2021), "Conway's influence on the study of random tilings", <a href="The_Mathematical_Intelligencer" title="The Mathematical Intelligencer">The Mathematical Intelligencer</a>, 43 (2): 40–46, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs00283-021-10089-3">10.1007/s00283-021-10089-3</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=4278473">4278473</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:236397105">236397105</a></cite>

</li>

<li id="cite_note-watkins-22">^ <a href="#cite_ref-watkins_22-0">a</a> <a href="#cite_ref-watkins_22-1">b</a> <cite id="CITEREFWatkins2004" class="citation cs2">Watkins, John J. (2004), Across the Board: The Mathematics of Chessboard Problems, Princeton University Press, pp. <a rel="nofollow" class="external text" href="https://archive.org/details/acrossboardma00watk/page/12">12–14</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-691-11503-0</bdi></cite>

</li>

<li id="cite_note-wright-23">^ <a href="#cite_ref-wright_23-0">a</a> <a href="#cite_ref-wright_23-1">b</a> <cite id="CITEREFWright2014" class="citation cs2">Wright, Colin (2014), <a rel="nofollow" class="external text" href="https://www.solipsys.co.uk/Writings/TheMutilatedChessBoardRevisited.pdf">"The mutilated chess board (revisited)"</a> (PDF), Recreational Mathematics Magazine (1): 4–9, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=3323392">3323392</a>, <a rel="nofollow" class="external text" href="https://web.archive.org/web/20220808180737/https://www.solipsys.co.uk/Writings/TheMutilatedChessBoardRevisited.pdf">archived</a> (PDF) from the original on 2022-08-08, retrieved 2022-07-18</cite>

</li>

<li id="cite_note-thurston-24"><a href="#cite_ref-thurston_24-0">^</a> <cite id="CITEREFThurston1990" class="citation cs2"><a href="William_Thurston" title="William Thurston">Thurston, William P.</a> (1990), "Conway's tiling groups", <a href="The_American_Mathematical_Monthly" title="The American Mathematical Monthly">The American Mathematical Monthly</a>, 97 (8): 757–773, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F2324578">10.2307/2324578</a>, <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2324578">2324578</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1072815">1072815</a></cite>

</li>

<li id="cite_note-urquhart-25"><a href="#cite_ref-urquhart_25-0">^</a> <cite id="CITEREFUrquhart2003" class="citation cs2">Urquhart, Alasdair (2003), "Resolution proofs of matching principles", Annals of Mathematics and Artificial Intelligence, 37 (3): 241–250, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1023%2FA%3A1021231610627">10.1023/A:1021231610627</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1969128">1969128</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:6753523">6753523</a></cite>

</li>

<li id="cite_note-bpmb-26"><a href="#cite_ref-bpmb_26-0">^</a> <cite id="CITEREFCodelReevesHeuleBryant2021" class="citation cs2 cs1-prop-long-vol">Codel, Cayden R.; Reeves, Joseph E.; <a href="Marijn_Heule" title="Marijn Heule">Heule, Marijn J. H.</a>; Bryant, Randal E. (2021), <a rel="nofollow" class="external text" href="https://www.cs.cmu.edu/~jereeves/research/bipart-paper.pdf">"Bipartite perfect matching benchmarks"</a> (PDF), in Balyo, Tomáš; Froleyks, Nils; Heule, Marijn; Iser, Markus; Järvisalo, Matti; Suda, Martin (eds.), Proceedings of SAT Competition 2021: Solver and Benchmark Descriptions, Department of Computer Science Report Series B, vol. B-2021-1, Helsinki: Department of Computer Science, University of Helsinki, pp. 52–53, <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/10138%2F333647">10138/333647</a>, <a rel="nofollow" class="external text" href="https://web.archive.org/web/20220718194032/https://www.cs.cmu.edu/~jereeves/research/bipart-paper.pdf">archived</a> (PDF) from the original on 2022-07-18, retrieved 2022-07-18</cite>

</li>

<li id="cite_note-semidefinite-27"><a href="#cite_ref-semidefinite_27-0">^</a> <cite id="CITEREFde_KlerkVan_MaarenWarners2000" class="citation cs2">de Klerk, Etienne; Van Maaren, Hans; Warners, Joost P. (2000), <a rel="nofollow" class="external text" href="https://research.tilburguniversity.edu/en/publications/relaxations-of-the-satisfiability-problem-using-semidefinite-prog">"Relaxations of the satisfiability problem using semidefinite programming"</a>, <a href="Journal_of_Automated_Reasoning" title="Journal of Automated Reasoning">Journal of Automated Reasoning</a>, 24 (1–2): 37–65, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1023%2FA%3A1006362203438">10.1023/A:1006362203438</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1750258">1750258</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:5727281">5727281</a>, <a rel="nofollow" class="external text" href="https://web.archive.org/web/20210620184800/https://research.tilburguniversity.edu/en/publications/relaxations-of-the-satisfiability-problem-using-semidefinite-prog">archived</a> from the original on 2021-06-20, retrieved 2022-07-19</cite>

</li>

<li id="cite_note-andrews-bishop-28"><a href="#cite_ref-andrews-bishop_28-0">^</a> <cite id="CITEREFAndrewsBishop1996" class="citation cs2">Andrews, Peter B.; Bishop, Matthew (1996), <a rel="nofollow" class="external text" href="https://gtps.math.cmu.edu/tw96.ps.Z">"On sets, types, fixed points, and checkerboards"</a>, in Miglioli, Pierangelo; Moscato, Ugo; Mundici, Daniele; Ornaghi, Mario (eds.), Theorem Proving with Analytic Tableaux and Related Methods, 5th International Workshop, TABLEAUX '96, Terrasini, Palermo, Italy, May 15–17, 1996, Proceedings, Lecture Notes in Computer Science, vol. 1071, Springer, pp. 1–15, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-61208-4_1">10.1007/3-540-61208-4_1</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-61208-7</bdi>, <a rel="nofollow" class="external text" href="https://web.archive.org/web/20220718075425/https://gtps.math.cmu.edu/tw96.ps.Z">archived</a> from the original on 2022-07-18, retrieved 2022-07-18, <q>most treatments of the problem in the literature solve it in the conceptual sense, but do not actually provide proofs of the theorem in either of McCarthy's original formulations</q></cite>

</li>

<li id="cite_note-dantchev-riis-29"><a href="#cite_ref-dantchev-riis_29-0">^</a> <cite id="CITEREFDantchevRiis2001" class="citation cs2">Dantchev, Stefan S.; Riis, Søren (2001), <a rel="nofollow" class="external text" href="https://dro.dur.ac.uk/670/1/">"'Planar' tautologies hard for resolution"</a>, <a href="Symposium_on_Foundations_of_Computer_Science" title="Symposium on Foundations of Computer Science">42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14–17 October 2001, Las Vegas, Nevada, USA</a>, IEEE Computer Society, pp. 220–229, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FSFCS.2001.959896">10.1109/SFCS.2001.959896</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:18849777">18849777</a>, <a rel="nofollow" class="external text" href="https://web.archive.org/web/20220914190415/https://dro.dur.ac.uk/670/1/">archived</a> from the original on 2022-09-14, retrieved 2022-07-18</cite>

</li>

<li id="cite_note-alekhnovich-30"><a href="#cite_ref-alekhnovich_30-0">^</a> <cite id="CITEREFAlekhnovich2004" class="citation cs2">Alekhnovich, Michael (2004), "Mutilated chessboard problem is exponentially hard for resolution", <a href="Theoretical_Computer_Science_(journal)" title="Theoretical Computer Science (journal)">Theoretical Computer Science</a>, 310 (1–3): 513–525, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0304-3975%2803%2900395-5">10.1016/S0304-3975(03)00395-5</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2020358">2020358</a></cite>

</li>

<li id="cite_note-razborov-31"><a href="#cite_ref-razborov_31-0">^</a> <cite id="CITEREFRazborov2004" class="citation cs2"><a href="Alexander_Razborov" title="Alexander Razborov">Razborov, Alexander A.</a> (2004), <a rel="nofollow" class="external text" href="http://people.cs.uchicago.edu/~razborov/files/matching.pdf">"Resolution lower bounds for perfect matching principles"</a> (PDF), <a href="Journal_of_Computer_and_System_Sciences" title="Journal of Computer and System Sciences">Journal of Computer and System Sciences</a>, 69 (1): 3–27, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.jcss.2004.01.004">10.1016/j.jcss.2004.01.004</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2070797">2070797</a>, <a rel="nofollow" class="external text" href="https://web.archive.org/web/20220808151212/http://people.cs.uchicago.edu/~razborov/files/matching.pdf">archived</a> (PDF) from the original on 2022-08-08, retrieved 2022-07-19</cite>

</li>

<li id="cite_note-korf-32"><a href="#cite_ref-korf_32-0">^</a> <cite id="CITEREFKorf1980" class="citation cs2">Korf, Richard E. (1980), "Toward a model of representation changes", <a href="Artificial_Intelligence_(journal)" title="Artificial Intelligence (journal)">Artificial Intelligence</a>, 14 (1): 41–78, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0004-3702%2880%2990033-8">10.1016/0004-3702(80)90033-8</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0587851">0587851</a></cite>

</li>

<li id="cite_note-krishnamurthy-33"><a href="#cite_ref-krishnamurthy_33-0">^</a> <cite id="CITEREFKrishnamurthy1985" class="citation cs2">Krishnamurthy, Balakrishnan (1985), "Short proofs for tricky formulas", <a href="Acta_Informatica" title="Acta Informatica">Acta Informatica</a>, 22 (3): 253–275, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF00265682">10.1007/BF00265682</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0806206">0806206</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:2459540">2459540</a></cite>

</li>

<li id="cite_note-clausal-34"><a href="#cite_ref-clausal_34-0">^</a> <cite id="CITEREFHeuleKieslBiere2019" class="citation cs2"><a href="Marijn_Heule" title="Marijn Heule">Heule, Marijn J. H.</a>; Kiesl, Benjamin; Biere, Armin (2019), "Clausal proofs of mutilated chessboards", in Badger, Julia M.; <a href="Kristin_Yvonne_Rozier" title="Kristin Yvonne Rozier">Rozier, Kristin Yvonne</a> (eds.), NASA Formal Methods – 11th International Symposium, NFM 2019, Houston, TX, USA, May 7–9, 2019, Proceedings, Lecture Notes in Computer Science, vol. 11460, Springer, pp. 204–210, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-030-20652-9_13">10.1007/978-3-030-20652-9_13</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-030-20651-2</bdi>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:92989148">92989148</a></cite>

</li>

<li id="cite_note-isabelle-35"><a href="#cite_ref-isabelle_35-0">^</a> <cite id="CITEREFPaulson2001" class="citation cs2">Paulson, Lawrence C. (2001), <a rel="nofollow" class="external text" href="https://www.cl.cam.ac.uk/~lp15/papers/Reports/mutil.pdf">"A simple formalization and proof for the mutilated chess board"</a> (PDF), Logic Journal of the IGPL, 9 (3): 475–485, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1093%2Fjigpal%2F9.3.475">10.1093/jigpal/9.3.475</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1828741">1828741</a>, <a rel="nofollow" class="external text" href="https://web.archive.org/web/20220808125039/https://www.cl.cam.ac.uk/~lp15/papers/Reports/mutil.pdf">archived</a> (PDF) from the original on 2022-08-08, retrieved 2022-07-18</cite>

</li>

<li id="cite_note-mizar-36"><a href="#cite_ref-mizar_36-0">^</a> <cite id="CITEREFRudnicki1996" class="citation cs2 cs1-prop-long-vol">Rudnicki, Piotr (1996), <a rel="nofollow" class="external text" href="https://era.library.ualberta.ca/items/ae7346a0-6a95-433b-bb8c-5a35900329d1">The Mutilated Checkerboard Problem in the Lightweight Set Theory of Mizar</a>, Technical Report, vol. TR96-09, University of Alberta Department of Computer Science, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.7939%2FR3QV3C738">10.7939/R3QV3C738</a>, <a rel="nofollow" class="external text" href="https://web.archive.org/web/20220718200746/https://era.library.ualberta.ca/items/ae7346a0-6a95-433b-bb8c-5a35900329d1">archived</a> from the original on 2022-07-18, retrieved 2022-07-18</cite>

</li>

<li id="cite_note-subramanian-37"><a href="#cite_ref-subramanian_37-0">^</a> <cite id="CITEREFSubramanian1996" class="citation cs2">Subramanian, Sakthi (1996), "An interactive solution to the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\times n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n\times n}</annotation>

</semantics>

</math><img src="./59d2b4cb72e304526cf5b5887147729ea259da78.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.63ex; height:1.676ex;" alt="{\displaystyle n\times n}" loading="lazy"> mutilated checkerboard problem", <a href="Journal_of_Logic_and_Computation" title="Journal of Logic and Computation">Journal of Logic and Computation</a>, 6 (4): 573–598, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1093%2Flogcom%2F6.4.573">10.1093/logcom/6.4.573</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1406233">1406233</a></cite>

</li>

<li id="cite_note-wazir-38"><a href="#cite_ref-wazir_38-0">^</a> <cite id="CITEREFBivensHolshouserKlein2008" class="citation cs2">Bivens, Irl C.; Holshouser, Arthur L.; Klein, Benjamin G. (October 2008), "Wazir circuits on an obstructed chessboard", <a href="Mathematics_Magazine" title="Mathematics Magazine">Mathematics Magazine</a>, 81 (4): 276–284, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1080%2F0025570X.2008.11953562">10.1080/0025570X.2008.11953562</a>, <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/27643123">27643123</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:125950546">125950546</a></cite>

</li>

<li id="cite_note-hanson-nash-39"><a href="#cite_ref-hanson-nash_39-0">^</a> <cite id="CITEREFHansonNash2018" class="citation cs2">Hanson, Mary Grace; Nash, David A. (Spring 2018), "Minimal and maximal Numbrix puzzles", <a href="Pi_Mu_Epsilon_Journal" class="mw-redirect" title="Pi Mu Epsilon Journal">Pi Mu Epsilon Journal</a>, 14 (8): 505–514, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1706.09389">1706.09389</a></cite>

</li>

<li id="cite_note-debruijn-40"><a href="#cite_ref-debruijn_40-0">^</a> <cite id="CITEREFde_Bruijn1969" class="citation cs2"><a href="Nicolaas_Govert_de_Bruijn" title="Nicolaas Govert de Bruijn">de Bruijn, N. G.</a> (1969), <a rel="nofollow" class="external text" href="https://research.tue.nl/nl/publications/filling-boxes-with-bricks(e45f1645-f5f4-4f3c-8370-0a8d26d470d8).html">"Filling boxes with bricks"</a>, <a href="The_American_Mathematical_Monthly" title="The American Mathematical Monthly">The American Mathematical Monthly</a>, 76 (1): 37–40, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F2316785">10.2307/2316785</a>, <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2316785">2316785</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0234841">0234841</a></cite>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .side-box{margin:4px 0;box-sizing:border-box;border:1px solid #aaa;font-size:88%;line-height:1.25em;background-color:var(--background-color-interactive-subtle,#f8f9fa);display:flow-root}.mw-parser-output .infobox .side-box{font-size:100%}.mw-parser-output .side-box-abovebelow,.mw-parser-output .side-box-text{padding:0.25em 0.9em}.mw-parser-output .side-box-image{padding:2px 0 2px 0.9em;text-align:center}.mw-parser-output .side-box-imageright{padding:2px 0.9em 2px 0;text-align:center}@media(min-width:500px){.mw-parser-output .side-box-flex{display:flex;align-items:center}.mw-parser-output .side-box-text{flex:1;min-width:0}}@media(min-width:720px){.mw-parser-output .side-box{width:238px}.mw-parser-output .side-box-right{clear:right;float:right;margin-left:1em}.mw-parser-output .side-box-left{margin-right:1em}}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1237033735">

/* start https://en.wikipedia.org/ */

@media print{body.ns-0 .mw-parser-output .sistersitebox{display:none!important}}@media screen{html.skin-theme-clientpref-night .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}

/* end https://en.wikipedia.org/ */

</style><div class="side-box side-box-right sistersitebox"><style data-mw-deduplicate="TemplateStyles:r1126788409">

/* start https://en.wikipedia.org/ */

.mw-parser-output .plainlist ol,.mw-parser-output .plainlist ul{line-height:inherit;list-style:none;margin:0;padding:0}.mw-parser-output .plainlist ol li,.mw-parser-output .plainlist ul li{margin-bottom:0}

/* end https://en.wikipedia.org/ */

</style>

<div class="side-box-text plainlist">Wikimedia Commons has media related to <a href="https://commons.wikimedia.org/wiki/Category:Mutilated_chessboard_problem" class="extiw external" title="commons:Category:Mutilated chessboard problem">Mutilated chessboard problem</a>.</div></div>

</div>

<ul><li><a rel="nofollow" class="external text" href="http://demonstrations.wolfram.com/GomorysTheorem/">Gomory's Theorem</a> by Jay Warendorff, <a href="The_Wolfram_Demonstrations_Project" class="mw-redirect" title="The Wolfram Demonstrations Project">The Wolfram Demonstrations Project</a>.</li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-08-02" href="https://en.wikipedia.org/wiki/?title=Mutilated_chessboard_problem&oldid=1303773446">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>